package combinatorics;

/**
 * author :  apurv verma
 * email  :  dapurv5@gmail.com
 */

public class MyCombinations {
	
	private static int n=0;
	private static int r=0;
	private static Object C[][];
	private static int count=0;
	public static int nCr=0;
	
		
	public static int factorial(int num){
		int f=1;
		for(int i=1;i<=num;i++){
			f=f*i;
		}
		return f;
	}
	
	
	public static Object[][] combinations(Object[] List,int R){
		
		n=List.length;
		r=R;
		nCr=factorial(n)/(factorial(r)*factorial(n-r));
		int A[]=new int[r];
		A[0]=1;
		for(int i=1;i<r;i++){
			A[i]=A[i-1]+1;
		}
		
		C=new Object[nCr][r];		
		helperCombinations(A,List);
		return C;
	}
	
	/*
	 * A.length==r represents number of nested loops.
	 * Initial value of A[i] represents the initial value of ith nested loop
	 * l represents the terminal value of ith nested loop.
	 */
	private static void helperCombinations(int A[],Object List[]){
		
		for(int i=0;i<r;i++){
			
			if(A[i]>n){
				if(i==0)
					return;
				
				int k=i;
				while(A[k]>n && k!=0){
						A[k-1]++;
						k--;
				}
				for(int j=k+1;j<A.length;j++){
					A[j]=A[j-1]+1;
				}
				
				helperCombinations(A,List);
				return;
			}
		}
		
		for(int j=0;j<r;j++){
			C[count][j]=List[A[j]-1];
			//UNCOMMENT TO PRINT ALL COMBINATIONS
			//System.out.print(List[A[j]-1]);
		}
		count++;
		//System.out.println();
		A[r-1]++;
		helperCombinations(A,List);
		
	}

}
